package leetcode.median;

import leetcode.base.TreeNode;

import java.util.HashMap;

/**
 * ClassName: $106_BuildTree
 * Description:
 * date: 2021-12-07 16:25
 *
 * @author liyifan
 */
public class $106_BuildTree {
    HashMap<Integer, Integer> indexMap = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0;i < inorder.length;i++) {
            indexMap.put(inorder[i], i);
        }
        return recur(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }
    public TreeNode recur(int[] in, int[] post, int in_left, int in_right, int post_left, int post_right){
        if (in_left > in_right) {
            return null;
        }
        int rootVal = post[post_right];
        TreeNode root = new TreeNode(rootVal);
        int rootIndex = indexMap.get(rootVal);
        int rightSize = in_right - rootIndex;
        root.left = recur(in, post, in_left, rootIndex - 1, post_left, post_right - rightSize - 1);
        root.right = recur(in, post, rootIndex + 1, in_right, post_right - rightSize + 1, post_right - 1);

        return root;
    }
}
